/*
 * @Author: gggg 1263457581@qq.com
 * @Date: 2025-06-03 09:09:57
 * @LastEditors: gggg 1263457581@qq.com
 * @LastEditTime: 2025-06-06 18:16:08
 * @FilePath: /algorithm-and-data-struct/algorithm/string/KMP.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */


/*生成KMP搜索所需的next数组,next数组代表模式串和文本串匹配失败后模式串应该跳到哪个位置 */
void BBEncMvList::genNextArray(uint8_t* pattern, int* next, int len)
{
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j < len - 1)
    {
        if (k == -1 || pattern[j] == pattern[k]) 
        {
            k++;
            j++;
            if (pattern[j] != pattern[k]) next[j] = k;
            else next[j] = next[k];
        }
        else 
        {
            k = next[k];
        }
    }
}


/* KMP算法， pattern对应输入的小块一列像素, text对应输入的一列像素 */
void BBEncMvList::Kmp(uint8_t *pattern, uint8_t *text, int pattern_size, int text_size, std::set<int> &can_location)
{
    //int* next = (int*)malloc(sizeof(int) * pattern_size);
    genNextArray(pattern, next, pattern_size);
    
    int i = 0;
    int j = 0;
    while (i < text_size)
    {
        /* 如果当前字符匹配成功， 则文本串(一列像素)和模式串(小块列像素)标都右移 */
        if(j == -1 || pattern[j] == text[i]) 
        {
            i++;
            j++;
        }
        else 
        {
            /* 匹配失败，则跳到next数组指示位置 */
            j = next[j];
        }

        if (j == pattern_size) 
        {
            int position = (i - j) / pixel_stride;
            int mod = (i - j) % pixel_stride;
            if (mod == 0) {
                can_location.insert(position);
            }
            i = i - pattern_size; 
            j = -1;
        }
    }
    //free(next);
}